#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define RANGE 10000000

int * arrGen(int number){

    if(number <= 0){

        return NULL;
    }
    int * array = (int *)malloc(sizeof(int)*number);
    if(NULL == array){

        printf("malloc failed.\n");
        return NULL;
    }
    for(int index = 0;index < number;++index){

        array[index] = rand() % 1000;
    }
    return array;
}
int checkSortedArray(int * array,int number){

    int index_iter = 1;
    for(int index = 0;index < number && index_iter < number;++index_iter,++index){

        if(array[index] > array[index_iter]){

            printf("check failed,on array[%d] : %d > array[%d] : %d.\n",index,array[index],index_iter,array[index_iter]);
            return -1;
        }
    }
    return 1;
}
void printArray(int * array,int number){

    for(int index = 0;index < number;++index){

        printf("%d . ",array[index]);
    }
    printf("\n");
}
void quickSortHelp(int * array,int low,int high){

    if(low >= high){

        return;
    }
    int base  = array[low];
    int first = low;
    int last  = high;
    while(low < high){

        while(high > low && array[high] >= base){

            high--;
        }
        if(low < high){

            array[low++] = array[high];
        }
        while(high > low && array[low] <= base){

            low++;
        }
        if(low < high){

            array[high--] = array[low];
        }
    }
    // low and high is equal
    array[low] = base;
    quickSortHelp(array,first,low-1);
    quickSortHelp(array,low+1,last);
}
void quickSort(int * array,int number){

    quickSortHelp(array,0,number-1);
}

int main(int argc,char * argv[]){

    if(argc < 2){

        printf("need one position integer.\n");
        return EXIT_FAILURE;
    }
    if(argc == 3){

        srand(strtol(argv[2],NULL,10));
    }else{

        srand(time(NULL));
    }
    int number = (int)strtol(argv[1],NULL,10);
    int * array = arrGen(number);

    // printArray(array,number);
    quickSort(array,number);
    // printArray(array,number);
    checkSortedArray(array,number);

    free(array);
    return EXIT_SUCCESS;
}

